The present invention relates to draw processing method and apparatus, and more particularly to draw processing method and apparatus having a draw function suitable to high speed clipping of a horizontal or vertical line segment.
In a prior art draw processing apparatus such as that disclosed in Japanese Unexamined Patent Publication No. 58-203550 when a line segment AB to be drawn having a gradient in a range of 0.degree.-45.degree. is drawn by using a Bresenham algorithm (see "Algorithm for Computer Control of a Digital Plotter", Bresenham, J. E., IBM System Journal, Vol. 4, No. 1, pages 25-30, 1965) for line generation shown in FIG. 1, coordinates of a series of dot points constituting the line segment AB are sequentially generated based on a rule that a point to be plotted next to a point A is either a righthand point or a right upward point.
If the draw processing is completed by plotting all of the series of coordinate points thus generated, there would be no problem. Usually, however, a rectangular area of a predetermined draw area as shown by a hatched area in FIG. 2 is given and only the series of coordinate points within this area are plotted and the coordinate points beyond this area are inhibited for plotting (clipping). In such clipping, a 4-bit area code is generated based on two-dimension coordinates (xi, yi) of the generated coordinate point P and position information LX, TY, RX and BY of the draw rectangular area, and if all of the four bits are zero, the coordinate point P is plotted and in other cases, the plotting is inhibited. This can be attained by a circuit shown in FIG. 3. Of the four bits of the area code, TC is a flag to indicates that the coordinate point xi, yi is above the area, BC is a flag to indicate that it is below the area, LC is a flag to indicate that it is on the left of the area, and RC is a flag to indicate that it is on the right of the flag.
On the other hand, in a graphic pattern generation algorithm which can process faster than the Bresenham algorithm shown in FIG. 1, horizontally (or vertically) continuous series of coordinate points shown in FIG. 4 are handled as a horizontal (or vertical) segment and a graphic pattern is drawn by specifying a start coordinate of the segment and a segment length (run length). In this algorithm, if the gradient is smaller than 45.degree. as shown in FIG. 4, an increment .DELTA.Y on a Y coordinate is smaller than an increment .DELTA.X on an X coordinate, and the increment .DELTA.X on the X coordinate is distributed to grid pitches of the Y coordinate where the increment on the X coordinate per grid pitch of the Y coordinate is equal to the run length of the segment. Since the increment per grid pitch is usually not an integer, it is represented by a formula shown in FIG. 4 where R is an integer part and .DELTA.R is a fraction part. At the opposite ends of the line, .DELTA.X/2.DELTA.Y is used to half the decrement. Since the run length must be an integer, an error is generated if R is used as the run length when .DELTA.R is not zero. When an accumulation of the error exceeds 1, the run length is set to R+1 and in other cases, it is set to R. In this manner, the sloped line shown in FIG. 4 is drawn.
In order to aid the understanding of the algorithm, the example shown in FIG. 4 is explained. Since .DELTA.X=22 and .DELTA.Y=5, R=4 and .DELTA.R=0.4. At the ends of the line, they are divided by two and r=2 and .DELTA.r=0.2. Thus, the run length of the first segment is 2, but since the start point is not included, 1 is added so that the run length is equal to 3. The error is equal to .DELTA.r or 0.2. The run length of the next segment is equal to R or 4 because the error is equal to .DELTA.r+.DELTA.R=0.6 which is smaller than 1. The run length of the third segment is equal to R+1 or 5 because the error is equal to 0.6+.DELTA.R=1. Since the error exceeding 1 is reflected to the run length, the fraction portion of 0 is the error. The above steps are repeated until the end point is reached to obtain the result shown in FIG. 4. Unlike the Bresenham algorithm in which individual coordinates are determined, this algorithm determines the start positions of the horizontal segments and the lengths thereof and hence provides a higher coordinate determination efficiency.
Accordingly, the output data for the graphic pattern generation algorithm in which the coordinate is determined for the horizontal or vertical segment include the coordinate point P (xi, yi), run length R and direction coefficient D (horizontal segment or vertical segment), as a result, in the example of FIG. 4, six coordinate calculations are required compared to 22 coordinate calculations in the case of the Bresenham algorithm, and only the horizontal or vertical lines needs to be drawn. Thus, a fast processing is achieved.
However, as shown in FIG. 2, if only a portion of the screen can be drawn and the clipping is done for each of the coordinate points shown in FIG. 3, the horizontal or vertical segment is converted to a series of points and the clipping is done for each point. As a result, 22 coordinate points are calculated as are done in the Bresenham algorithm and the drawing performance is not improved.